The present invention relates generally to configuring the topology of a communications network, and more specifically to a system and method for detecting and eliminating network loops connected to a bridge device installed in a networking hub.
As it is generally known, in a local area network (LAN) using a protocol such as Ethernet or Token Ring, devices referred to as “nodes” compete for the ability to use a shared communications path to exchange messages referred to as “data units” or “frames.” However, if too many nodes consistently attempt to transmit simultaneously, the overall performance of the network may potentially be affected, even to the point of bringing communications over the network to a near halt. To make this possibility less likely, large LANs are often divided into two or more LAN segments connected by one or more networking devices referred to as “bridges.” In such a configuration, each data unit is received by any bridge or bridges connected to the LAN segment on which the data unit originated. Each bridge then determines which segment or segments the received data unit should be forwarded to, and only forwards the data unit to that segment or segments. In this way, data units transmitted between nodes within a single segment are isolated from other segments, thus reducing traffic on those other segments.
A bridge determines which LAN segments to forward a received data unit onto based on destination address information within the data unit and a data structure reflecting the locations of nodes within the various interconnected LAN segments, referred to as the forwarding table or forwarding tables of the bridge. Each bridge learns where specific nodes are located by examining the MAC source addresses of data units it receives, and by forming associations between those MAC source addresses and the segments on which the data units containing them were received. In the case where a data unit is received having a destination address for which no destination segment is known, a bridge typically broadcasts that data unit onto all segments to which it is connected, to ensure that the data unit is received at its intended destination node. This approach is generally referred to as “transparent bridging”, which is performed by a “learning bridge.” Transparent bridging is advantageous in that it does not require setup of the forwarding tables by a network administrator.
A known problem relating to the use of bridge technology is the need to avoid what are referred to as “broadcast storms.” Broadcast storms may occur when bridges are connected in a physical loop, which results in a logical loop sometimes referred to as a “bridge loop.” A bridge loop occurs when data units can travel from a first LAN segment to a second LAN segment through more than one path. In order to eliminate bridge loops, existing bridge devices typically employ a technique referred to as the spanning tree algorithm. The spanning tree algorithm is implemented by bridges interchanging special messages known as Bridge Protocol Data Units (“BPDUs”). The specific format of BPDUs is described in IEEE 802.1. The spanning tree algorithm calls for various specific types of BPDUs to be sent by bridges to a special multicast address that is received by all bridges.
The spanning tree algorithm includes steps to (1) elect a single bridge from the connected bridges to be the “root” bridge, (2) calculate a best path distance to the “root” bridge from each other bridge, (3) identify a “designated bridge” for each LAN segment that will be used for forwarding packets towards the root bridge, (4) choose a port on each bridge that gives the best path towards the root, and (5) select ports to be included within the spanning tree. Using the bridge elected as a root bridge for reference, the spanning tree algorithm operates to switch one of any two bridges forming a physical loop in the network into a standby mode, so that only one side of a potential bridge loop passes traffic. By listening to configuration update BPDUs, a bridge in the standby mode can switch automatically from standby mode into forwarding mode in the event that the other bridge forming the physical loop fails. The spanning tree protocol thus ensures that physical loops in the network topology do not result in logical looping of network traffic.
While the spanning tree algorithm has proven generally effective in eliminating bridge loops, implementing the spanning tree algorithm on relatively low cost bridging devices may be prohibitively costly. For example, hardware logic necessary to perform the spanning tree algorithm typically includes a spanning tree state register for each port in a bridge. The value stored in such a state register maintains a current spanning tree state for the associated port. In a bridge device supporting the spanning tree algorithm, a spanning tree state register is necessary for each port in the device, since the value of the register effects forwarding decisions made by the bridge. Accordingly, in a bridge device designed for relatively low cost applications, but containing a significant number of ports, hardware circuitry to provide a spanning tree state register for each port may add undesirable costs to the overall design. Additionally, it may be desirable in some circumstances to limit the network topologies which may be connected to a given port or ports of a relatively low cost bridging device. For example, in the case where a bridging device is designed for relatively small network configurations, it may include a relatively small forwarding table. It would be undesirable for large, complex networks, having large numbers of nodes, to be attached to a port of such a device. Accordingly, it may be desirable to have a system which further operates to prevent the attachment of large, complex networks to one or more ports of a relatively low cost bridging device.
For the reasons stated above, it would be desirable to have a system for avoiding bridge loops and the potential broadcast storms which may result from them, but which does not require the relatively costly implementation of the spanning tree algorithm within a relatively low cost bridge device. The system should further be applicable to bridge devices wishing to limit the types of topologies which are connected to one or more of their external ports.